Máy Turing

Máy Turing là một mô hình toán học cho một máy tính tổng quát. Nó là một thiết bị lý thuyết thao tác trên các ký hiệu nằm trên một dải băng. Máy Turing không nhằm thiết kế thiết bị tính toán trên thực tế, mà chỉ là một thiết bị trừu tượng đại diện cho máy tính. Người ta tin rằng nếu một vấn đề có thể được giải quyết bởi một thuật toán, thì cũng có một máy Turing giải quyết vấn đề đó. Tất cả các mô hình tính toán hiện nay chẳng hạn như máy RAM, Trò chơi cuộc sống của Conway, automat tế bào, hay bất kì ngôn ngữ lập trình nào cũng đều có thể tính được trên máy Turing. Do máy Turing phù hợp cho việc nghiên cứu bằng toán học, và được xem là mạnh ngang bất kì mô hình tính toán nào, máy Turing là mô hình tính toán phổ biến nhất trong lý thuyết độ phức tạp tính toán.

Các mô hình khác

Có nhiều mô hình khác ngoài mô hình chuẩn máy Turing nhiều băng đã được nghiên cứu, chẳng hạn như máy truy cập ngẫu nhiên. Tất cả các mô hình này đều có thể được chuyển hóa lẫn nhau mà không cần thêm khả năng tính toán đặc biệt nào. Tuy vậy, thời gian và bộ nhớ của các mô hình khác nhau có thể khác nhau.[1].

Các thông số độ phức tạp

Để định nghĩa cụ thể thời gian và bộ nhớ cần thiết để giải quyết một vấn đề, cần định rõ một mô hình tính toán cụ thể, chẳng hạn như máy Turing tất định. Thời gian cần thiết cho một máy Turing M giải quyết dữ liệu vào x là số lượng lần chuyển trạng thái, hay số bước, của máy trước khi máy ngừng và thông báo kết quả ("có" hoặc "không"). Một máy Turing chạy trong thời gian f(n) nếu thời gian máy sử dụng cho tất cả các dữ liệu vào kích thước n là không quá f(n). Có thể định nghĩa lượng bộ nhớ cần thiết một cách tương tự như vậy. Mặc dù thời gian và bộ nhớ là hai thông số phổ biến nhất, nhiều thông số phức tạp khác cũng có thể xem là tài nguyên tính toán. Các thông số độ phức tạp được định nghĩa tổng quát bởi các tiên đề độ phức tạp Blum. Một vài thông số độ phức tạp khác được dùng trong lý thuyết độ phức tạp bao gồm độ phức tạp truyền thông, độ phức tạp mạch, và độ phức tạp cây quyết định.